package leetcode;

/**
 * Created by Ghost on 2014/9/24 0024.
 */
public class TwoSum {
    class ListNode2{
        int val;
        int index;
        ListNode2 next;
        ListNode2(int x, int ind) {
            val = x;
            index = ind; 
            next = null;
        }
    }
    public int[] twoSum(int[] numbers, int target){
        int[] rst = new int[2];
        int max = 0;
        for(int i=0;i<numbers.length;i++){
            if(max<Math.abs(numbers[i]))
                max = Math.abs(numbers[i]);
        }
        ListNode2[] tmp = new ListNode2[max+1];
        for(int i=0;i<numbers.length;i++){
            int n = Math.abs(numbers[i]);
            if(tmp[n]==null){
                tmp[n] = new ListNode2(numbers[i],i+1);

            }
            else
                tmp[n].next = new ListNode2(numbers[i],i+1);
        }
        for(int i=0;i<tmp.length;i++){
            if(tmp[i]==null)
                continue;
            else{
                int a1 = tmp[i].val;
                int index1 = tmp[i].index;
                int needb1 = target - a1;
                int index = Math.abs(needb1);
                if(index>=0 && index < tmp.length){
                    ListNode2 tmpp = tmp[index];
                    while(tmpp!=null){
                        if(tmpp.val==needb1 && tmpp.index!=index1){
                            if(index1<tmpp.index ){
                                rst[0] = index1;
                                rst[1] = tmpp.index;
                            }
                            else{
                                rst[0] = tmpp.index;
                                rst[1] = index1;
                            }
                            return rst;
                        }
                        tmpp = tmpp.next;
                    }
                }
                if(tmp[i].next!=null){
                    int a2 = tmp[i].next.val;
                    int index22 = tmp[i].next.val;
                    int needb2 = target - a2;
                    int index2 = Math.abs(needb2);
                    if(index2>=0 && index2 < tmp.length){
                        ListNode2 tmpp = tmp[index2];
                        while(tmpp!=null){
                            if(tmpp.val==needb2 && tmpp.index!=index22){
                                if(index22<tmpp.index){
                                    rst[0] = index22;
                                    rst[1] = tmpp.index;
                                }
                                else{
                                    rst[0] = tmpp.index;
                                    rst[1] = index22;
                                }
                                return rst;
                            }
                            tmpp = tmpp.next;
                        }
                    }
                }
            }
        }
        return null;
    }
    public static void main(String[] args){
        int[] numbers = new int[] {0,4,3,0};
        TwoSum TwoSum = new TwoSum();
        int[] rst = TwoSum.twoSum(numbers, 0);
        System.out.println(rst[0]+" "+rst[1]);
    }
}
